package bintree.heap.LeetCode;

import java.util.*;

//373. 查找和最小的 K 对数字 ——找最小值，就用最大堆
//请找到和最小的 k 个数对 (u1,v1),  (u2,v2)  ...  (uk,vk) 。
public class Num373_kSmallestPairs {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        //创建优先级队列，其中队列中保存Pair对象，传入比较器，使得和越小反而越大
        Queue<Pair> queue = new PriorityQueue<>(new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return (o2.u + o2.v) - (o1.u + o1.v);
            }
        });
        //遍历两个数组，其中u来自第一个数组，v来自第二个数组
        //并不需要把所有可能都保存，因为是两个升序数组，取k个数对
        //就遍历两个数组的前k个元素即可，如：k = 2,2 * 2 就有4种可以满足了
        //还有一种可能，如果原数组本身长度就小于 k，那么用的还是原来数组的长度
        //所以需要判断k和数组长大小，取小的遍历即可
        for (int i = 0; i < Math.min(nums1.length, k); i++) {
            for (int j = 0; j < Math.min(nums2.length, k); j++) {
                if(queue.size() < k){
                    queue.offer(new Pair(nums1[i], nums2[j]) );
                }else{
                    //判断元素是否需要入队列
                    Pair tmp = queue.peek();//查看队列第一个元素值
                    int add = nums1[i] + nums2[j];//新元素
                    if(add < (tmp.u + tmp.v) ){
                        queue.poll();//出队列
                        //因为队列保存的Pair所以必须new该类对象往里面存放值
                        queue.offer(new Pair(nums1[i], nums2[j]));
                    }

                }
            }

        }//for
        //3. 此时队列中就已经保存了和最小的前 k个Pair对象，取出其中的u和v保存到数组里即可
        List<List<Integer>> ret = new ArrayList<>();//创建保存元素的二维数组
        while(!queue.isEmpty()){
            Pair pair = queue.poll();//弹出一个元素
            //因为ret里面传入的类型就是 List<Integer> 所以就用这个类型来保存
            List<Integer> list = new ArrayList<>();
            list.add(pair.u);
            list.add(pair.v);
            ret.add(list);
        }
        return ret;
    }
}

// 自定义一个类，每次保存两个数组中的一个元素
class Pair{
    int u;//保存数组1的元素
    int v;//保存数组2的元素

    public Pair(int u, int v) {
        this.u = u;
        this.v = v;
    }
}